package kyssion.leetcode.num51_100;

public class code60_第k个排列 {
    public static void main(String[] args) {
        System.out.println(new code60_第k个排列().getPermutation(2,1));
    }

    int[] ins = new int[]{
            1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
    };

    public String getPermutation(int n, int k) {
        char[] item = new char[n];
        boolean[] use = new boolean[10];
        int speed = 0;
        int length = n;
        while (k != 0) {
            int now = k / ins[--n];
            int next = k - now * ins[n];
            if (next != 0) {
                now += 1;
            }
            for (int a = 1, s = 0; a <= length; a++) {
                if (!use[a] && ++s == now) {
                    item[speed++] = (char) ('0' + a);
                    use[a]=true;
                    break;
                }
            }
            k = next;
        }
        while (speed < length) {
            for (int a = length; a >=1 ; a--) {
                if (!use[a] && speed < length) {
                    item[speed++] = (char) ('0' + a);
                }
            }
        }
        return new String(item);
    }
}
